（以下内容主要是进阶指南上的题目，如果有推荐可以联系我再添加）

石子合并

（原链接：https://www.luogu.com.cn/problem/P1880）
题目大意：在一个圆形的操场上放置了 $N$ 堆石块，现在要按某种次序把所有的石块合并成一堆，规定每次合并的时候仅能合并相邻的两堆（注意环上可以相连），每次操作时花费为两堆石子个数之和，问所有的操作可能性中能得到的最小与最大花费是多少。

思路

环形肯定不好做，考虑把环给破坏掉，同时还得保证信息能够正确统计。

具体来说，由于有 $N$ 堆石子，合并 $N-1$ 次，所以一定会有一堆石子是只出去的，一堆石子是只进来的，而且他俩在环上的位置相邻。

如果把合并到别的堆看做是一条边的话，那么整个环上就一定有一对点之间是不直接相连而是与别的点相连的，我们可以在这里画一条线破开整个环。但是我们并不知道哪个点与哪个点之间是破开的，所以我们枚举所有情况：
①首先把整条环的序列拉成两倍长，这样可以以顺时针或者逆时针的一种顺序统计出顺时针与逆时针旋转的两种情况。
②枚举每个点开始的长度为 $N$ 的序列，统计序列上的本问题的答案即可。

第②问就是一个简单的区间DP了，简单来说就是以区间为集合进行状态转移，每次合并的时候都是两个相邻的已经各自合并好的区间进行合并，直接做即可，最终统计两种信息:一种是最小花费一种是最大花费。具体的dp定义和状态转移就不展开了，比较简单，后面附上代码。

代码

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 207;
int fup[N][N],fdw[N][N],a[N],s[N];
int main()
{
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i)
    {
        scanf("%d",&a[i]);
        a[i + n] = a[i];
        s[i] = s[i - 1] + a[i];
    }    
    for(int i = n+1;i <= 2 * n;++i)
        s[i] = s[i - 1] + a[i];
    for(int len = 2;len <= n;++len)
    {
        for(int l = 1;l + len - 1 <= 2*n;++l)
        {
            int r = l + len - 1;
            fdw[l][r] = 0x3f3f3f3f;
            for(int k = l;k < r;++k)
            {
                fup[l][r] = max(fup[l][r],fup[l][k] + fup[k+1][r] + s[r] - s[l - 1]);
                fdw[l][r] = min(fdw[l][r],fdw[l][k] + fdw[k+1][r] + s[r] - s[l - 1]);
            }
        }
    }
    int dres = 0x3f3f3f3f,ures = 0;
    for(int i = 1;i <= n;++i)
        dres = min(dres,fdw[i][i + n - 1]),ures = max(ures,fup[i][i + n - 1]);
    printf("%d\n%d",dres,ures);
    return 0;
}

拓展内容

本题的数据加强版有一个叫GarsiaWachs的算法据说专门解决这个问题

[IOI1998]多边形Polygon

原题链接：https://www.luogu.com.cn/problem/P4342
题意较难描述，请自行前往原地址查看题目

思路

首先第一步要拆掉一条边，在上一个石子合并这个题目里我们就知道了如果两两合并一定会有一对节点之间是不直接相连的，也就是说“删除掉了”。其次一个大的区间也是由两个小的区间合并而来的，所以这个题基本套上一个题目的板子来就可以了，直接维护一个最大值。

但是，这个题存在着负数和乘号的合并，就有一个问题：我取两个区间最终合并的最大值，并不一定能拿到整个区间最终能合并出的最大值，假设说左边的区间最大值是负数而右边的最大值是正数而最小值是负数，那么显然以左区间的最大值和右区间的最大值乘出来的结果还不如左区间的最大值和右区间的最小值相乘（注意这里也不是最大值，具体看稍后的分析，这里只是说这种操作也不如他）。也就是说在本题中，我们还得额外的记录一下：合并出的最小值是多少。

记左区间的最大值和最小值分别为 $lf和lg$ ，右区间的分别为 $rf和rg$ 。
①两个区间是加法的情况，显然直接以最大值和最小值只之和合并即可
②两个区间是乘法的情况：
我们分别来考虑：
（以下++&++的形式左边的两个符号是表示 $lf和$ lg$的正负情况，右边的两个符号同理）

（1）++&++
显然最大值 $F = lf * rf$ 最小值 $G = lg * rg$
（2）++&-+
$F = lf * rf$
$G = lf* rg$
（3）++&--
$F = lg * rf$
$G = lf * rf$
（4）-+&-+
$F = max(lf * rf,lg * rg)$
$G = min(lf * rg,lg * rf)$
（5）-+&--
$F = lg * rg$
$G = lf * rf$
（6）--&--
$F = lg * rg$
$G = lf * rf$
其余情况对称处理。
综上我们还可以合并一下，对于最大值F来说，他肯定是由： $lf*rf或lg*rg或lg*rf或lf*rg$ 中的一种，所以直接全部枚举一下就可以了，不存在是否合法的问题。同样的，对于最小值G来说也有对应的 $lg*rg或lf*rg或lg*rf或lf*rf$ 。故直接维护即可。
不过在具体代码中，还需要分析一下合并的符号具体是取哪，细节问题看代码。
本题就是石子合并维护信息上的拓展

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 55 * 4,INF = 0x3f3f3f3f;
int a[N],f[N][N],g[N][N];
char opt[N];
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);
    int n;cin >> n;
    for(int i = 1;i <= n;++i)
    {
        cin >> opt[i] >> a[i];
        a[i + n] = a[i];
        opt[i + n] = opt[i];
    }
    for(int len = 1;len <= n;++len)
    {
        for(int l = 1;l + len - 1 <= n * 2;++l)
        {
            int r = l + len - 1;
            if(len == 1)    f[l][r] = g[l][r] = a[l];
            else
            {
                f[l][r] = -INF;g[l][r] = INF;
                for(int k = l;k < r;++k)
                {
                    int lf = f[l][k],lg = g[l][k],rf = f[k + 1][r],rg = g[k + 1][r];
                    if(opt[k + 1] == 't')
                    {
                        f[l][r] = max(f[l][r],lf + rf);
                        g[l][r] = min(g[l][r],lg + rg);
                    }
                    else
                    {
                        f[l][r] = max(f[l][r],max(max(lf * rf,lg * rf),max(lg * rg,lf * rg)));
                        g[l][r] = min(g[l][r],min(min(lg * rg,lf * rg),min(lg * rf,lf * rf)));                        
                    }
                }
            }
        }
    }
    int res = 0;
    for(int i = 1;i <= n;++i)   res = max(res,f[i][n + i - 1]);
    cout << res << endl;
    for(int i = 1;i <= n;++i)
        if(res == f[i][i + n - 1])
            cout << i << " ";
    return 0;
}

[USACO]Naptime

原题链接:https://www.luogu.com.cn/problem/P6064
题目大意：一天划分成 $N$ 个小时，一个人每天要在里面选出总长为B个时间段睡觉。这个人会在时间的分界点上入睡，且开始入睡的第一个小时之后每休息一个小时都会得到一个相应的收益 $U_i$ ，由当前时间 $i$ 决定。其次这个人每天都会按同样的休息方式休息，而且时间也是连续的，问他怎么选择时间可以使得收益和最大。

思路

我们先来看一下，如果说时间是不连续的，整个区间是线性的，怎么来做：
状态: $f[i,j,k]$ 表示当前在第 $i$ 段时间，已经睡了 $j$ 个时间段， $k=0$ 时表示没在睡觉，反之表示正在睡觉。

入口: $f[1][0][0] = f[1][1][1] = 1$ ，其余为负无穷
出口: $max(f[n][b][0],f[n][b][1])$

转移：
$f[i][j][0] = max(f[i - 1][j][0],f[i - 1][j][1])$
$f[i][j][1] = max(f[i - 1][j - 1][0],f[i - 1][j - 1][1] + U_i)$
（特别注意题目中的第一段时间睡觉是不计入收益的）

那么，我们可以很简单的找到说单纯的一个序列问题，得到的最大结果是多少，接下来我们来考虑怎么把他拓展到原来题目的环形状态，我们发现，本来的环形状态里，如果最大的那种方案不包含从 $N$ 睡到 $1$ 的部分，那么我们上面求出的这个答案就是最大的答案，所以我们可以想办法做第二次DP，能求出这个额外的一种跨越了一整天的情形，就可以解决这个问题了。考虑修改一下原来的状态定义：
入口: $f[1][1][1] = U_1$ ，其余为负无穷
出口 $f[n][b][1]$
我们把入口规定成跨越了一整天的情形，并且把其他的所有状态全部换成不合法的负无穷值，这就使得第二次的dp过程是只有这一种缺掉的情况的，同时出口也规定了一定是在睡觉的情况，得以求出正确的答案。
转移一致
最终我们把两次DP结果的出口答案取一个最大值，就是整个的最大值。

不过呢，这道题还有最后一步要特别指出，题目是只有64MB的（详见洛谷另一道题），因此如果直接把空间开成 $N*N*2$ 的话会MLE，这个题的转移方程是可以滚动数组优化的，倒序即可。
细节问题详见代码。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 4000;
int f[N][2],U[N];
int n,m;
int dp(int k)
{
    for(int i = 2;i <= n;++i)
        for(int j = m;j >= 0;--j)
        {
            f[j][0] = max(f[j][0],f[j][1]);
            if(j >= 1)  f[j][1] = max(f[j - 1][0],f[j - 1][1] + U[i]);
        }
    if(k == 0)  return max(f[m][0],f[m][1]);
    return f[m][1];
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= n;++i)   scanf("%d",&U[i]);
    memset(f,-0x7f,sizeof f);
    f[0][0] = 0;
    f[1][1] = 0;
    int res = dp(0);
    memset(f,-0x7f,sizeof f);
    f[1][1] = U[1];
    res = max(res,dp(1));
    printf("%d\n",res); 
    return 0;
}

拓展内容

感觉这个做法其实可以把第一道石子合并拓展一下？没有验证，如果可以我会以后写上的。

环路运输

原题链接：https://www.acwing.com/problem/content/291/
题目大意：在一个环形公路上有编号1~N的N个仓库，定义 $i$ 号仓库和 $j$ 号仓库之间的距离是 $dist(i,j)=min(|i - j|,N - |i - j|)$ （就是在顺时针和逆时针两种情形下选短的一条）。每个仓库里都有一定量的货物，记他们的重量为 $A_i$ ，那么两个仓库之间运输货物的距离就是 $A_i+A_j + dist(i,j)$ ，现在要求在哪两个仓库之间运送货物是消耗最大的。
数据范围： $1 \leq N \leq 10^6$

思路

这个数据范围太大了，得是 $O(N)$ 级最多带个 $log$ 。
显然我们是无法避免枚举两个点中的一个点的，不妨把问题换成：对每个点 $i$ 来说，那个点 $j$ 与他的距离会是最大的。不过首先，我们还是来考虑一下怎么破坏环结构到序列上。
首先由于顺逆时针环形的存在，我们先定义一个 $len=n/2$ ，假如说两点的距离大于len则肯定要选另一个方向上的距离了。

还是把整个环拆成两倍成，对于序列上的一个点 $i$ 来说：
原来的环上，逆时针往回走的 $j$ 就是序列里在 $i$ 的左侧的一个点
①假如说满足条件: $i - j >= len$ ，实际的消耗表达式就是 $A_i + A_j + i - j$ 。
②若不满足上述表达式，则选择 $j+N$ ，实际的消耗表达式就是 $A_i + A_j + j + N - i$
如果在拓展了两倍长的环上，在>N的部分继续查，第②步里的 $j+N$ 就可以作为 $i$ 向前找，等价于第一种情况，所以我们可以只找对于每一个 $i$ 往前的最大值。
具体来说，对我们当前枚举的 $i$ 来说，计算的消耗中 $A_i + i$ 是固定的，我们只需要找一个 $j∈[i - len,i - 1]$ ，他的 $A_j - j$ 的值是最大的，就可以了。很显然，就是一个单调队列维护的区间最值题，详细看代码吧。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e6+7;
int a[N * 2],q[N * 2];
int main()
{
    int n;scanf("%d",&n);
    for(int i = 1;i <= n;++i)   scanf("%d",&a[i]),a[i + n] = a[i];
    int hh = 0,tt = -1,res = 0;
    for(int i = 1;i <= 2 * n;++i)
    {
        if(hh <= tt && q[hh] < i - n / 2)   ++hh;
        res = max(res,a[i] + i + a[q[hh]] - q[hh]);
        while(hh <= tt && a[q[tt]] - q[tt] <= a[i] - i) --tt;
        q[++tt] = i;
    }
    printf("%d",res);
    return 0;
}

其他题目

③Kaavi and Magic Spell 区间DP
链接：https://www.luogu.com.cn/problem/CF1336C
一道不错的区间DP题，状态的设计上有一定的难度，我之后可能会补在这篇文章里或者单独写一下，看具体情况吧。
④积蓄程度区间DP&DFS序
链接：https://www.acwing.com/problem/content/289/
将树上的信息转换成序列再统计的一道题，也有一定的难度，来自进阶指南
⑤合唱团
链接：https://www.luogu.com.cn/problem/P3205
貌似是个经典题，但是我没做（咕咕咕）先放这里，如果不合适我再删掉
（先放在这里吧，有补充再说）

环形结构上的动态规划

石子合并

思路

代码

拓展内容

相关题目

[IOI1998]多边形Polygon

思路

代码

[USACO]Naptime

思路

代码

拓展内容

环路运输

思路

代码

其他题目

感谢您的支持，我会继续努力的!